Single Number

LeetCode 136 | Difficulty: Easy

Easy

Problem Description

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

- `1 <= nums.length <= 3 * 10^4`

- `-3 * 10^4 <= nums[i] <= 3 * 10^4`

- Each element in the array appears twice except for one element which appears only once.

Topics: Array, Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 96 ms)

Metric	Value
Runtime	96 ms
Memory	26.3 MB
Date	2020-04-04

Solution

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = nums[0];
    for (int i = 1; i < nums.Length; i++)
    {
        result ^= nums[i];
    }
    return result;
    }
}

📜 2 more C# submission(s)

Submission (2022-02-21) — 141 ms, 39.8 MB

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = nums[0];
    for (int i = 1; i < nums.Length; i++)
    {
        result ^= nums[i];
    }
    return result;
    }
}

Submission (2017-11-12) — 202 ms, N/A

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = nums[0];
    for (int i = 1; i < nums.Length; i++)
    {
        result ^= nums[i];
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Think about the XOR (^) operator's property.